The present invention relates to Digital Signal Processing (DSP) in general, and more particularly to methods and apparatus for improved xe2x80x9cin-placexe2x80x9d memory pointer management in support of Fast Fourier Transform (FFT) calculations.
A Digital Signal Processor. (DSP) is a special-purpose computer that is designed to optimize digital signal processing tasks such as Fast Fourier Transformation (FFT), digital filtering, image processing, and speech recognition. DSP applications are typically characterized by real-time operation, high interrupt rates, and intensive numeric computations. In addition, DSP applications tend to be intensive in memory access operations and require the input and output of large quantities of data.
FFT data are made up of a sequence of N data points, where one data point comprises two data values, one real and one imaginary. The data points are grouped into N/2 xe2x80x9cAxe2x80x9d data points and N/2 xe2x80x9cBxe2x80x9d data points where each FFT butterfly operation as shown in FIG. 1 operates on one A data point (AR,AI) and one B data point (BR,BI) together with various coefficients (WR,WI) to yield (XR,XI) and (YR,YI) which provide the A and B data points for the next stage of the FFT operation. The selection of data points as A and B data points for each FFT butterfly operation varies with each stage of the FFT.
The following table labeled Table 1xe2x80x94FFT (A,B) Groupings illustrates the (A,B) data point groupings required for each stage of an FFT having a sequence of 16 data points numbered 0 through 15.
The following table labeled Table 2xe2x80x94FFT A/B Dispositions illustrates the A/B disposition of each FFT data point at each stage of a 16-data point FFT:
In DSP architectures that perform FFT calculations data are read from and written to memory in several stages. Some DSP architectures employ separate memory spaces for input data and output data. In such a memory arrangement the results of one FFT stage may be written in the order of the A and B data point selection of the next stage, allowing for incremental advancing of pointers to the A and B data point memory addresses. The following table labeled Table 3xe2x80x94A/B Sort Order illustrates a theoretical FFT data point ordering that is pointer-optimized for each stage of a 16-data point FFT:
In order to reduce the amount of memory required for FFT, xe2x80x9cin-placexe2x80x9d memory management schemes have been developed whereby the FFT input data memory space is overwritten with the results of FFT calculations, thus eliminating the need for an additional memory space for storing the results at each stage of the FFT. Unfortunately, such a memory arrangement results in the data points being stored in memory in data point sort order as shown in Table 2 rather than in A/B sort order as shown in Table 3 for stages subsequent to stage 0, thus precluding incremental advancing of pointers to the A and B data point memory addresses. While memory address look-up tables or hard-coded memory addresses may be used, such approaches negate the memory efficiencies of xe2x80x9cin-placexe2x80x9d FFT.
The present invention seeks to provide methods and apparatus for improved xe2x80x9cin-placexe2x80x9d memory pointer management in support of Fast Fourier Transform (FFT) calculations.
There is thus provided in accordance with a preferred embodiment of the present. invention a method for advancing pointers in a memory including a sequence of N data points of a stage M of a Fast Fourier Transform (FFT) whose first stage is stage 0, the N data points including N/2 A data points and NV/2 B data points, the N data points are stored in the memory in 2M groupings of A data points, each of the groupings having 2(Log2N)xe2x88x921xe2x88x92M data points, and each of the groupings is followed by a grouping of 2(Log2N)xe2x88x921xe2x88x92M B data points, the method including the steps of a) setting a pointer index Ap equal to the binary value of the data point memory index corresponding to the first A data point in the memory, b) setting a pointer index Bp equal to the binary value of the data point memory index corresponding to the first B data point in the memory, c) setting a first binary bit mask value R1 equal to 2(Log2N)xe2x88x921xe2x88x92M+1, d) setting a second binary bit mask value R2 equal to 2(Log2N)xe2x88x921xe2x88x92M, e) advancing the Bp pointer index to the data point memory index corresponding to the next B data point in the memory by e1) adding the Ap pointer index value to R1, e2) ORing the results of step e1) with R2, and e3) setting the Bp pointer index value equal to the results of step e2), and f) advancing the Ap pointer index to the data point memory index corresponding to the next A data point in the memory by f1) adding the Ap pointer index value to R1, f2) ANDing the results of step f1) with the bit-inverted value of R2, and f3) setting the Ap pointer index value equal to the results of step f2).
Further in accordance with a preferred embodiment of the present invention the method further includes repeating steps e) and f) more than one time.
Still further in accordance with a preferred embodiment of the present invention the method further includes repeating steps e) and f) until the Ap pointer index equals the data point memory index corresponding to the last of the A data points in the memory and the Bp pointer index equals the data point memory index corresponding to the last of the B data points in the memory.
It is appreciated throughout the specification and claims that the term xe2x80x9cdata pointxe2x80x9d refers to a pairing of two data values, a real value and an imaginary value.
It is also appreciated throughout the specification and claims that the term xe2x80x9cdata point memory indexxe2x80x9d refers to the minimum number of addressing bits needed to uniquely identify one data point from another within a single memory space.